1. Field of the Invention
The invention concerns caching of data in networks generally and more specifically concerns the caching of queryable data in network servers.
2. Description of the Prior Art
Once computers were coupled to communications networks, remote access to data became far cheaper and easier than ever before. Remote access remained the domain of specialists, however, since the available user interfaces for remote access were hard to learn and hard to use. The advent of World Wide Web protocols on the Internet have finally made remote access to data available to everyone. A high school student sitting at home can now obtain information about Karlsruhe, Germany from that city""s Web site and a lawyer sitting in his or her office can use a computer manufacturer""s Web site to determine what features his or her new PC ought to have and then configure, order, and pay for the PC.
A consequence of the new ease of remote access and the new possibilities it offers for information services and commerce has been an enormous increase in the amount of remote access. This has in turn lead to enormous new burdens on the services that provide remote access and the resulting performance problems are part of the reason why the World Wide Web has become the World Wide Wait.
FIG. 1 shows one of the causes. of the performance problems. At 101, there is shown the components of the system which make it possible for a user at his or her PC to access an information source via the World Wide Web. Web browser 103 is a PC which is running Web browser software. The Web browser software outputs a universal resource locator (URL) 104 which specifies the location of a page of information in HTML format in the World Wide Web and displays HTML pages to the user. The URL may have associated with it a message containing data to be processed at the site of the URL as part of the process of obtaining the HTML page. For example, if the information is contained in a database, the message may specify a query on the data base. The results of the query would then be returned as part of the HTML page. Internet 105 routes the URL 104 and its associated message to the location specified by the URL, namely Web server 107. There, HTML program 109 in Web server 107 makes the HTML page 106 specified by the URL and returns it to Web browser 103. If the message specifies a query on the database in database server 115, HTML program 109 hands the message off to Web application program 111, which translates the message into a query in the form required by data access layer 112.
Data access layer 112 is generally provided by the manufacturer of database server 115. It takes queries written in standard forms such as OLE-DB, ODBC, or JOBC, converts the queries into the form required by database server 115, and places the queries in messages in the form required by network 113. Database server 115 then executes the query and returns the result via network 113 to data access layer 112, which puts the results into the required standard form and returns them to Web application 111, which in turn puts the result into the proper format for HTML program 109. HTML program 109 then uses the result in making the HTML page 106 to be returned to browser 103.
As may be seen from the above description, a response to a URL specifying a page whose construction involves database server 115 requires four network hops: one on Internet 105 from browser 103 to Web server 107, one on network 113 from server 107 to server 115, one on network 113 from server 115 to server 107, and one on Internet 105 from server 107 to browser 103. If more than one query is required for an HTML page, there will be a round trip on network 113 for each query.
Moreover, as shown at 117, a typical Web transaction is a series of such responses: the first HTML page includes the URL for a next HTML page, and so forth. The transaction shown at 117 begins with a request for an HTML page that is a form which the user will fill out to make the query; data base server 115 provides the information for the HTML page. When that page is returned, the user fills out the form and when he or she is finished, the browser returns a URL with the query from the form to server 107, which then deals with the query as described above and returns the result in another HTML page. That page permits the user to order, and when the user orders, the result is another query to database server 115, this time, one which updates the records involved in the transaction.
Not only do Web transactions made as shown in FIG. 1 involve many network hops, they also place a tremendous burden on data base server 115. For example, if data base server 115 belongs to a merchant who sells goods on the Web and the merchant is having a special, many of the;transactions will require exactly the same sequence of HTML pages and will execute exactly the same queries, but because system 101 deals with each request from a web browser individually, each query must be individually executed by database server 115.
The problems of system 101 are not new to the designers of computer systems. There are many situations in a computer system where a component of the system needs faster access to data from a given source, and when these situations occur, the performance of the system can be improved if copies of data that is frequently used by the component are kept at a location in the system to which the component has faster access than it has to the source of the data. When such copies exist, the location at which the copies are kept is termed a cache and the data is said to be cached in the system.
Caching is used at many levels in system 101. For example, browser 103 keeps a cache of previously-displayed HTML pages, so that, it can provide a previously-displayed HTML page to the user without making a request for the page across Internet 105. Web server 107 similarly may keep a cache of frequently-requested HTML pages, so that it can simply return the page to the user, instead of constructing it. Database server 115, finally, may keep a cache of the information needed to answer frequently-made queries, so that it can return a result more quickly than if it were starting from scratch. In system 101, the most effective use of caching is in Web server 107, since data that is cached there is still accessible to all users of internet 105, while the overhead of the hops on data access 113 is avoided.
Any system which includes caches must deal with two problems: maintaining consistency between the data in the cache and the data in the data source and choosing which data to cache. In system 101, the first problem is solved in the simplest way possible: it is the responsibility of the component using the data to determine when it needs a new copy of the data from the data source. Thus, in browser 103, the user will see a cached copy of a previously-viewed HTML page unless the user specifically clicks on his browser""s xe2x80x9creloadxe2x80x9d button. Similarly, it is up to HTML program 109 to determine when it needs to redo the query that provided the results kept in a cached HTML page. The second problem is also simply solved: when a new page is viewed or provided, it replaces the least recently-used cached page.
Database systems such as the Oracle8(trademark) server, manufactured by Oracle Corporation and described in Leverenz, et al., Oracle8 Server Concepts, release 8.0, Oracle Corporation, Redwood City, Calif., 1998., move a copy of a database closer to its users by replicating the original database at a location closer to the user. The replicated data base may replicate the entire original or only a part of it. Partial replications of a database are termed table snapshots. Such table snapshots are read-only. The user of the partial replication determines what part of the original database is in the table snapshot. Consistency with the original database is maintained by snapshot refreshes that are made at times that are determined by the user of the table snapshot. In a snapshot refresh, the table snapshot is updated to reflect a more recent state of the portion of the original database contained in the snapshot. For details, see pages 30-5 through 30-11 of the Leverenz reference.
There are many applications for which the solution of letting the component that is doing the caching decide when it needs a new page causes problems. For example, when the information in a data source is important or is changing rapidly (for example, stock prices), good service to the user requires that the information in the caches closely tracks the information in the data source. Similarly, there are many situations where caching all data that has been requested causes problems. For instance, in a cache run according to least recently-used principles, any HTML page that is produced by HTML program 109 or received in browser 103 is cached and once cached, stays in the cache and takes up space that could be used for other HTML pages until it attains least recently-used status.
When Web server 107 includes a Web application 111 involving a database server 115, there is still another problem with caching in web server 107: since the data is cached in the form of HTML pages, it is not in queryable form, that is, a cached HTML page may contain data from which another query received from Web browser 103 could be answered, but because the data is contained in an HTML page instead of a database table, it is not in a form to which a query can be applied. Thus, even though the data is in server 107, server 107 must make the query, with the accompanying burden on data base server 115 and delays across network 113, and the HTML page containing the result of the query must be separately cached in server 107.
U.S. Ser. No. 09/294,656, Cusson, et al., Web servers with queryable dynamic caches, describes a web server 107 that has a cache in which cached data is to the extent possible in queryable form, in which the cached data is dependably updated when the data in the source changes, and in which selection of data from a source for caching is based on something other than the mere fact that a URL received from a web browser referenced the data, and thus provides a solution to the foregoing problems. The cache thus solves many of the problems of prior-art caches in network environments.
A remaining problem, however, is that the only way that Web server 107 can determine whether a query can be performed on the cache instead of on database server 115 is by doing the query on the cache and if a miss results, doing the query on database server 115. A query that goes to database server 115 as a result of a cache miss is thus substantially slower than one that goes directly to database server 115, and when there is a substantial number of cache misses, the result may be a substantial degradation of the overall performance of Web server 107 with a cache. It is an object of the present invention to make a query to database server 115 that results from a cache miss substantially as fast as a query that goes directly to database server 115.
The object is achieved by adding a miss table to a cache that contains copies of remotely-stored items. The query that is applied to the cache is in effect a specifier for the item that will be returned by the query. There may or may not be a copy of the item in the cache. If there is not, the remotely-stored item must be fetched. The miss table relates the specifier for the item to a status indicator that indicates at least whether the item is present in the cache. A dispatcher receives the specifier for the item and presents it to the miss table; if the miss table indicates that there is no copy of the item in the cache, the dispatcher uses the item specifier to fetch the remotely-stored data item.
The status indicator may further indicate that it is unknown whether there is a copy of the item in the cache. When the status indicator so indicates, the cache responds to the remote item specifier and provides an indication whether there is a copy of the item in the cache. A miss table manager for the miss table responds to the indication by updating the miss table in accordance with the indication. The cache further provides the miss table manager with a change event notification to the miss table manager when the contents of the cache have changed and the miss table manager responds thereto by setting the status for at least those items for which the status in the miss table indicates that there is no copy and which are affected by the change to unknown.
In an preferred embodiment, the miss table is employed in a network server that includes a cache. The cache may contain a copy of a rowset from a remote location and responds to a rowset specifier specifying the remote location by returning the rowset when there is a copy in the cache. The miss table relates the rowset specifier to a status indicator as described above. If the miss table indicates to the network server that there is no copy of the rowset in the cache, the network server fetches the rowset from the remote location.
Other objects and advantages will be apparent to those skilled in the arts to which the invention pertains upon perusal of the following Detailed Description and drawing, wherein: